In the field of computer resource management, the allocation of processor resources is performed in several ways. In single processor environments, the execution of a plurality of tasks may include the designation of each of the plurality of tasks as being of a certain priority level. The tasks are arranged in a queue and are subsequently provided to a processor that executes the tasks serially, giving each task a pre-emptive time-share of processing resources. During the execution of a task, a test may be performed in order to determine whether there are any tasks in the queue that are of a higher priority than the current task being executed. If the management system determines that there are tasks of higher priority than the current task being executed, then the current task may be desirably terminated and placed back into the queue in order to provide the higher priority task to the processor for execution. In this manner, the management system can provide desirably prompt execution of the highest priority tasks. This type of system is known as an interrupt system, and the switching of a task being executed from a lower priority task to a higher priority task is known as context-switching.
Within a single processor computer system, this type of operation is referred to as multitasking, and generally enables the virtual parallel execution of tasks on a single processor. In such a system, the multitasking operation is controlled by the kernel of an operating system (“OS”), where the kernel acts as an interface between the central processing unit (“CPU”) and the tasks to be executed. The kernel schedules the execution of the tasks such that the processor is shared between all of the tasks in the system. Accordingly, the kernel controls queue scheduling and priority handling, as described above.
The invention disclosed in U.S. Pat. No. 5,469,571 issued to Bunnell is an operating system architecture using multiple priority kernel task based interrupt handling. The kernel includes a scheduler which selects tasks for execution based on relative priority levels. The disclosure applies to the single processor environment.
Despite the desirably prompt performance of high priority tasks, the interrupt-based resource management systems described above present many drawbacks. Such drawbacks may include, for example, the loss of processing power and overhead incurred in the partial execution of a lower priority task that is terminated in order to process a higher priority task. Generally, this problem may be overcome by saving the progress of the lower priority task to, for example, a system memory and later restoring the progress when the task is ready to be finished. This saving step presents an undesirable need for large amounts of memory space, however, to store the progress of the lower priority task. Furthermore, the decision to terminate a lower priority process for a higher priority process may be performed several times, resulting in a plurality of partially processed tasks, each of which is undesirably using space in the memory. Another method of avoiding the problem identified above is in executing tasks in the processing queue in a run-to-completion fashion, whereby each task, once provided to the processor, cannot be recalled until it has been completely executed. This method may provide a further disadvantage in that higher priority tasks are no longer given precedence in execution and, therefore, are delayed by the execution of lower priority tasks.
A more desirable system for managing computing resources in execution of a plurality of tasks may organize the processing queue in such a fashion that the highest priority tasks are always ahead of the lower priority tasks, thereby reducing the need for interrupt systems and context switching. Such a system encounters a problem, however, when tasks, task priorities, or both are being added or changed in real time. This problem may undercut the expected efficiency of the originally organized queue and presents the need for continuous, real-time reorganization of the processing queue. Such a real-time reorganizing effort may be undesirably inefficient due to a relatively large size of the processing queue, as well as the low latency associated with sending and receiving tasks to and from the queue. Thus, it may be difficult to coordinate a full reorganization of the processing queue according to changes in the tasks and task priority before an occurrence of a further change in one or more tasks or task priorities, because such changes may be rapidly occurring.
The invention disclosed in U.S. Pat. No. 5,465,335 issued to Anderson relates to a multitasking data processing system that is provided with an operating system kernel. An event queue in the kernel stores task names awaiting placement in the processor queue. When an associated processor signals the occurrence of an event, matching logic searches all stores in the event queue, in parallel, to find a task associated with the signaled event and then transfers the task to the processor queue.
A further method that has been developed to overcome the undesirable aspects of single processor multitasking is a method known as multithreading. Multithreading is the sharing of a single processor between multiple tasks (i.e., threads) in a way designed to minimize the time required for context switching. This advantage is accomplished by sharing as much of the program execution environment as possible among different tasks in order to reduce the amount of task execution data that needs to be saved and restored when changing threads. Although multitasking attempts to hide thread resources corresponding to different threads, multithreading attempts to share as much of their environment as possible. Extensive multithreading may share, for example, a single address space and global variables set for separate threads distinguished only by the value of their program counts or stack pointers. Generally, multithreading may be used for very fine-grain tasks incorporating only a few basic instructions, so that resource management is desirably uncomplicated and less susceptible to errors. The extensive sharing of resources among the different threads being executed may render inadequate, however, the protection of resources dedicated to one thread from the execution of a different thread.
In order to overcome the inefficiencies of single-processor execution of a plurality of tasks, several systems utilizing multi-processor environments have been introduced and are now prevalent in the art. Such systems may utilize one or more processing queues in order to desirably provide a plurality of tasks to a plurality of processors available for computing, where the plurality of processors may have one or more dedicated processing resources and shared processing resources. The use of multi-processing also requires, however, an efficient and effective organization of the processing queue.
This requirement may be achieved through the use of multiple queues. The invention disclosed in U.S. Pat. No. 5,940,612 issued to Brady et al., for example, organizes tasks into multiple queues. Each queue represents a priority level and all tasks assigned to that queue are of that queue's designated priority level. The tasks are then sent to one or more processors for run-to-completion execution. Those tasks within the highest priority level queue are executed first. This system inherently provides real-time scheduling of tasks, whereby the organization of tasks into priority queues allows sequential execution of those tasks that have the highest priority down to those that have the lowest priority. When the highest priority queue is empty, the process will attempt to execute a task from the next highest priority queue, and so on. Therefore, in a situation where a higher priority queue is empty, a task from a lower priority queue may be executed. If one or more higher priority tasks are then added during the execution of the lower priority task, those higher priority tasks will be the next to be executed.
The method does not require an explicit reorganization and scheduling of an entire single queue in order to obtain an efficient execution of high priority tasks over lower priority tasks. The scheduling is automatically provided through the use of multiple priority queues which are drained sequentially. Such an implementation may provide several disadvantages such as, for example, an undesirable amount of time taken to evaluate the readiness of tasks within the multiple processing queues.
The invention disclosed in U.S. Pat. No. 5,938,708 issued to Wallace et al. relates to a multitasking operating system for a plurality of event queues under control of an event dispatcher, where the kernel dispatches events corresponding to processes. The invention is disclosed as including a single processor to execute a state-driven process that has control over the processor, or to execute a process not included in any state, such as a process of detecting vehicular collision. The invention also provides for assigning priority levels to the various processes.
U.S. Pat. No. 5,826,080 issued to Dworzecki is directed to a method of scheduling tasks to be executed in a serial processing system. The invention manages the sequence of tasks that must be executed serially by organizing them into execution queues representing processing time slots that correspond to desired run times for the tasks, respectively. Furthermore, the tasks may be formed into priority layers within an execution queue according to the order in which they must be performed.
A further problem that may arise in multi-processor environments is that of processor resource allocation and protection. In a multi-processor system, one or more processing queues may provide one or more tasks to the processors; the one or more tasks may be required to use the same processing resources. Although each processor in a multi-processor system has its own set of private processing resources, it also has access to a set of shared resources that are shared among the plurality of processors. Therefore, when multiple processors attempt to use the same resources in execution of a task, the entire multi-processing system may crash. In order to prevent such undesirable system crashes, a multi-processor system requires many levels of data communication among processors to avoid resource use conflicts, processor overloading, and processor idleness. Such a complicated system may be undesirably prone to errors. Furthermore, the data communication among processors may undesirably increase data latency and execution time, and decrease available bandwidth.
It may be recognized by those skilled in the art that the aforementioned task scheduling techniques and corresponding undesirability may generally relate to physical multi-processor and single-processor architectures, as well as virtual multi-processor architectures, such as those introduced by Intel Corporation's Hyper-Threading Technology. There remains a need, therefore, to overcome the shortcomings of existing systems for managing multiple processors in the execution of one or more processes in a task-based library platform.